# 题目描述：
# 包含n个整数的数组nums，找到三个数a,b,c，满足a+b+c=0，返回所有符合要求的数的下标列表
# 举例1:
# 输入：nums = [-1,0,1,2,-1,-4]
# 输出：[[-1,-1,2],[-1,0,1]]
# 例二：
# 输入：nums = []
# 输出：[]
# 例三：
# 输入：nums = [0]
# 输出：[]
# ======================================================================= #

from typing import List


class Solution:
    @staticmethod
    def threeSum(nums: List[int]) -> List[List[int]]:
        """
        两层循环，双指针法；
        收敛条件：1、当i+j+k=0时，j++并且k--;
                2、当i+j+k<0时，说明j太小了，需要往后找，故j++;
                3、当i+j+k>0时，说明k太大了，需要往前找，故k--;
                4、收敛中止条件：j == k;
        去重考虑：当i+j+k=0时，需要看一下j后面的数和k前面的数是不是相等，如果有相等，则j++或者k--跳过该数；
                即：while j < k and nums[j] == nums[j+1]: j += 1
        :param nums:
        :return:
        """

        # 优化点：先排序，如果nums[-1] < 0,则肯定找不到三个数,直接返回空即可
        nums.sort()
        if not nums or len(nums) < 3 or nums[-1] < 0:
            return []
        result = []
        for k in range(len(nums)):
            if nums[k] > 0:
                return result
            if k > 0 and nums[k] == nums[k - 1]:
                continue
            j, i = len(nums) - 1, k + 1
            while i < j:
                sums = nums[i] + nums[j] + nums[k]
                if sums == 0:
                    result.append([nums[k], nums[i], nums[j]])
                    while i < j and nums[i] == nums[i + 1]:
                        i += 1
                    while i < j and nums[j] == nums[j - 1]:
                        j -= 1
                    i += 1
                    j -= 1
                elif sums > 0:
                    j -= 1
                else:
                    i += 1

        return result


print(Solution().threeSum(nums=[0, 0, 0, 0, 0]))
